package com.hcl.linkedlist;

import java.util.Stack;

public class SingleLinkedListDemo {
    public static void main(String[] args) {
        SingleLinkedList singleLinkedList = new SingleLinkedList();
//        singleLinkedList.add(new HeroNode(1,"张杰","JsonZhang"));
//        singleLinkedList.add(new HeroNode(2,"张杰2","JsonZhang2"));
//        singleLinkedList.add(new HeroNode(3,"张杰3","JsonZhang3"));
        HeroNode heroNode1 = new HeroNode(2, "张杰1", "JsonZhang1");
        HeroNode heroNode = new HeroNode(1, "张杰", "JsonZhang");
        HeroNode heroNode2 = new HeroNode(3, "鹿晗", "luhan");


        singleLinkedList.addByOrder(heroNode);
        singleLinkedList.addByOrder(heroNode2);
        singleLinkedList.addByOrder(heroNode1);
//        singleLinkedList.update(heroNode2);
//        singleLinkedList.delete(1);
        singleLinkedList.list();
//        int length = getLength(singleLinkedList.getHead());
//        System.out.println("length = " + length);
//        HeroNode lastIndexNode = findLastIndexNode(singleLinkedList.getHead(), 1);
//        System.out.println("lastIndexNode = " + lastIndexNode);
//        reverseList(singleLinkedList.getHead());
//        singleLinkedList.list();
//        System.out.println("反转打印，不破坏数据结构");
//        reversePrint(singleLinkedList.getHead());

    }

    /**
     * 反转打印
     * 利用栈结构：先进后出
     * @param head
     */
    public static void reversePrint(HeroNode head){
        if (head.next == null){
            return;
        }
        Stack<HeroNode> stack = new Stack<>();
        HeroNode temp = head.next;
        while (temp != null){
            // 将各个节点压进栈中
            stack.push(temp);
            temp = temp.next;
        }
        // 遍历打印
        while (stack.size() > 0){
            System.out.println(stack.pop());
        }
    }

    /**
     * 反转链表
     * 思路：1、先定义了一个节点，reverseHead
     *      2、从头到尾遍历，每遍历一个节点就将其取出，并放在新的链表reverseHead的最前端
     *      3、将原来链表的head.next = reverseHead.next
     * @param head
     */
    public static  void reverseList(HeroNode head){
        HeroNode reverseHead = new HeroNode(0,"","");
        // 当链表为空，或者只有一个节点，则直接返回
        if (head.next == null && head.next.next == null){
            return;
        }
        // 定义一个辅助变量
        HeroNode temp = head.next;
        // 指向当前节点（temp）的下一个节点
        HeroNode next = null;
        while (temp!=null){
            // 先暂时保存当前节点的下一个节点，后面需要使用
            next = temp.next;
            // 将temp的下一个节点指向新链表的最前端
            temp.next = reverseHead.next;
            // 将temp连到最新的链表上
            reverseHead.next = temp;
            // 让temp后移
            temp = next;
        }
        // 将head.next指向reverseHead.next
        head.next = reverseHead.next;
    }

    /**
     * 查找单链表中倒数第k个节点
     * 先把链表遍历，得到链表长度
     * 然后从第一个开始遍历（size-index）个就可以得到
     * @param head
     * @param index
     * @return
     */
    public static HeroNode findLastIndexNode(HeroNode head, int index) {
        // 如果链表为空
        if (head.next == null){
            return null;
        }
        // 得到链表的长度
        int size = getLength(head);
        if (index <= 0 || index > size){
            return null;
        }
        // 定义一个辅助变量
        HeroNode temp = head.next; //3 //3-1=2
        for (int i = 0; i < (size - index); i++) {
            temp = temp.next;
        }
        return temp;
    }

    /**
     * 求单链表有效个数
     *
     * @return
     */
    public static int getLength(HeroNode head) {
        // 空链表
        if (head.next == null) {
            return 0;
        }
        // 定义一个辅助变量，不统计头节点
        HeroNode temp = head.next;
        int length = 0;
        while (temp != null) {
            length++;
            temp = temp.next;   // 遍历
        }
        return length;
    }
}
class SingleLinkedList {
    // 初始化头节点，头节点不要动，不存放具体的数据
    private HeroNode head = new HeroNode(0,"","");

    public HeroNode getHead() {
        return head;
    }

    /**
     * 添加节点到单向链表
     * 思路： 当不考虑编号时
     * 1、找到链表的最后节点
     * 2、将这个节点的next指向新的节点
     */
    public void  add(HeroNode heroNode){
        // 因为头节点不动，需要一个辅助遍历的temp
        HeroNode temp = head;
        while (true){
            if (temp.next == null){
                // 节点的下一个节点为空，说明已经到了最后一个节点
                break;
            }
            // 如果还没到到最后一个节点，继续遍历
            temp = temp.next;
        }
        // 走到这，说明到了最后一个节点，则将最后一个节点的next指向新的节点
        temp.next = heroNode;
    }

    /**
     * 删除
     * 找到要删除节点的前一个节点
     * @param no
     */
    public void delete(int no){
        HeroNode temp = head;
        boolean flag = false;
        while (true){
            if (temp.next == null){
                // 已经走到链表最后
                break;
            }
            if (temp.next.no == no) {
                // 删除节点
                flag = true;
                break;
            }
            // 节点后移
            temp = temp.next;
        }
        if (flag){
            temp.next = temp.next.next;
        } else {
            System.out.println("要删除的节点no"+ no +"不存在");
        }
    }

    /**
     * 修改
     */
    public void update(HeroNode heroNode){
        if (head.next==null){
            System.out.println("链表空");
            return;
        }
        // 头节点不动，需要一个temp辅助遍历
        HeroNode temp = head.next;
        boolean flag = false;
        while (true){
            if (temp.no == heroNode.no){
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if (flag){
            temp.name = heroNode.name;
            temp.nickname = heroNode.nickname;
        } else {
            System.out.println("没有找到编号为" + heroNode.no + "的数据");
        }
    }

    /**
     * 按照排名添加到指定位置
     * 如果有这个排名则添加失败
     * @param heroNode
     */
    public void addByOrder(HeroNode heroNode){
        // 因为头节点不动，需要一个辅助遍历,需要找到新节点的上一个节点
        HeroNode temp = head;
        boolean flag = false;
        while (true){
            // 节点的下一个节点为空，说明已经到了最后一个节点
            if (temp.next == null){
                break;
            }
            // 链表中已经存在
            if (temp.next.no == heroNode.no){
                flag = true;
                break;
            } else if (temp.next.no > heroNode.no) {
                break;
            }
            temp = temp.next;
        }
        if (flag){
            System.out.println("已经存在" + heroNode.no + "的数据");
        } else {
            heroNode.next = temp.next;
            temp.next = heroNode;
        }
    }

    /**
     * 遍历链表
     */
    public void list(){
        // 判断链表是否为空
        if (head.next==null){
            System.out.println("链表空");
            return;
        }
        // 因为头节点不能动，需要一个辅助变量来遍历
        HeroNode temp = head.next;
        while (true){
            // 判断是否到链表最后
            if (temp==null){
                break;
            }
            // 输出节点信息
            System.out.println(temp);
            // 将temp后移
            temp = temp.next;
        }
    }
}

class HeroNode{
    public int no;
    public String name;
    public String nickname;
    public HeroNode next;  // 下一个节点

    public HeroNode(int no, String name, String nickname) {
        this.no = no;
        this.name = name;
        this.nickname = nickname;
    }

    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                ", nickname='" + nickname + '\'' +
                '}';
    }
}
